﻿/*******************************************************************************************
 * Copyright (c) 2006-2009 Alex Robson, Rob Simmons, Craig Israel, and Rachel Twyford
 *
 * Use of this software in any form requires that you have both 
 * read and agreed to the following terms:
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the "Software"), 
 * to deal in the Software without restriction, including without limitation 
 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions: 
 *
 * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 * Redistributions in binary form must reproduce the above copyright notice, 
 * this list of conditions and the following disclaimer in the 
 * documentation and/or other materials provided with the distribution.
 * Neither the name of Nvigorate nor the names of its contributors may 
 * be used to endorse or promote products derived from this software without 
 * specific prior written permission. 
 *
 * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
 * DISCLAIMED. IN NO EVENT SHALL ANY CONTRIBUTOR BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * ****************************************************************************************/

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Nvigorate.Common
{
    public class Levenshtein
    {
        #region Distance Algorithms

        public static int Distance(string s1, string s2)
        {
            if (String.IsNullOrEmpty(s1)) 
                return String.IsNullOrEmpty(s2) ? 0 : s2.Length;
            
            if (String.IsNullOrEmpty(s2)) 
                return s1.Length;
            
            int c = 0; 
            int offset1 = 0; 
            int offset2 = 0; 
            int dist = 0; 
            
            while ((c + offset1 < s1.Length) && (c + offset2 < s2.Length))
            {
                if (s1[c + offset1] != s2[c + offset2])
                {
                    offset1 = 0; offset2 = 0; 
                    
                    for (int i = 0; i < 5; i++)
                    {
                        if ((c + i < s1.Length) && (s1[c + i] == s2[c]))
                        {
                            if (i > 0)
                            {
                                dist++; offset1 = i;
                            } 
                            goto ender;
                        } 
                        if ((c + i < s2.Length) && (s1[c] == s2[c + i]))
                        {
                            if (i > 0)
                            {
                                dist++; offset2 = i;
                            } 
                            goto ender;
                        }
                    } 
                    
                    dist++;
                } 
                
                ender: c++;
            } 
            
            return dist + (s1.Length - offset1 + s2.Length - offset2) / 2 - c;
        }

        /// <SUMMARY>Computes the Levenshtein Edit Distance between two enumerables.</SUMMARY>
        /// <TYPEPARAM name="T">The type of the items in the enumerables.</TYPEPARAM>
        /// <PARAM name="x">The first enumerable.</PARAM>
        /// <PARAM name="y">The second enumerable.</PARAM>
        /// <RETURNS>The edit distance.</RETURNS>
        public static int EditDistance<T>(IEnumerable<T> x, IEnumerable<T> y) where T : IEquatable<T>
        {
            // Validate parameters
            if (x == null) throw new ArgumentNullException("x");
            if (y == null) throw new ArgumentNullException("y");

            // Convert the parameters into IList instances
            // in order to obtain indexing capabilities
            IList<T> first = x as IList<T> ?? new List<T>(x);
            IList<T> second = y as IList<T> ?? new List<T>(y);

            // Get the length of both.  If either is 0, return
            // the length of the other, since that number of insertions
            // would be required.
            int n = first.Count, m = second.Count;
            if (n == 0) return m;
            if (m == 0) return n;

            // Rather than maintain an entire matrix (which would require O(n*m) space),
            // just store the current row and the next row, each of which has a length m+1,
            // so just O(m) space. Initialize the current row.
            int curRow = 0, nextRow = 1;
            int[][] rows = new int[][] { new int[m + 1], new int[m + 1] };
            for (int j = 0; j <= m; ++j) rows[curRow][j] = j;

            // For each virtual row (since we only have physical storage for two)
            for (int i = 1; i <= n; ++i)
            {
                // Fill in the values in the row
                rows[nextRow][0] = i;
                for (int j = 1; j <= m; ++j)
                {
                    int dist1 = rows[curRow][j] + 1;
                    int dist2 = rows[nextRow][j - 1] + 1;
                    int dist3 = rows[curRow][j - 1] +
                                (first[i - 1].Equals(second[j - 1]) ? 0 : 1);

                    rows[nextRow][j] = Math.Min(dist1, Math.Min(dist2, dist3));
                }

                // Swap the current and next rows
                if (curRow == 0)
                {
                    curRow = 1;
                    nextRow = 0;
                }
                else
                {
                    curRow = 0;
                    nextRow = 1;
                }
            }

            // Return the computed edit distance
            return rows[curRow][m];
        }

        public static int Similarity(string s1, string s2)
        {
            int dis = Distance(s1, s2); 
            
            int maxLen = Math.Max(s1.Length, s2.Length); 
            
            if (maxLen == 0) return 0; 

            else return dis;
        }

        public static int Traditional(string s, string t)
        {

            int n = s.Length; 
            int m = t.Length; 

            int[,] d = new int[n + 1, m + 1];
            int cost; 

            // Step 1

            if (n == 0) return m;
            if (m == 0) return n;

            // Step 2

            for (int i = 0; i <= n; d[i, 0] = i++) ;
            for (int j = 0; j <= m; d[0, j] = j++) ;

            // Step 3

            for (int i = 1; i <= n; i++)
            {
                //Step 4

                for (int j = 1; j <= m; j++)
                {
                    // Step 5

                    cost = (t.Substring(j - 1, 1) == s.Substring(i - 1, 1) ? 0 : 1);

                    // Step 6

                    d[i, j] = Math.Min(Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                                              d[i - 1, j - 1] + cost);

                }

            }

            // Step 7
            
            return d[n, m];
        }

        #endregion
        
        #region Value Pairing

        public static Dictionary<string, string> GetExclusiveMatches(List<string> inputs, List<string> values)
        {
            Dictionary<string, string> matches = new Dictionary<string, string>();

            Dictionary<string, SortedList<int, List<string>>> inputRank =
                new Dictionary<string, SortedList<int, List<string>>>();
            Dictionary<string, SortedList<int, List<string>>> valueRank =
                new Dictionary<string, SortedList<int, List<string>>>();

            List<string> usedValues = new List<string>();

            foreach (string input in inputs)
            {
                SortedList<int, List<string>> iRank = new SortedList<int, List<string>>();

                foreach (string value in values)
                {
                    SortedList<int, List<string>> vRank = valueRank.ContainsKey(value) ? 
                                                                                           valueRank[value]
                                                              : new SortedList<int, List<string>>();
                    if (vRank.Count == 0)
                    {
                        valueRank.Add(value, vRank);
                    }

                    int distance = EditDistance(input, value);
                    if (iRank.ContainsKey(distance))
                    {
                        iRank[distance].Add(value);
                    }
                    else
                    {
                        iRank.Add(distance, new List<string>(new string[] { value }));
                    }

                    if (vRank.ContainsKey(distance))
                    {
                        vRank[distance].Add(input);
                    }
                    else
                    {
                        vRank.Add(distance, new List<string>(new string[] { input}));
                    }
                }
                inputRank.Add(input, iRank);
            }

            foreach (string input in inputs)
            {
                foreach (KeyValuePair<int, List<string>> inputValuePair in inputRank[input])
                {
                    bool found = false;
                    foreach (string value in inputValuePair.Value)
                    {
                        if(usedValues.Contains(value))
                            continue;

                        if(valueRank[value][valueRank[value].Keys[0]].Contains(input))
                        {
                            matches.Add(input, value);
                            usedValues.Add(value);
                            found = true;
                            break;
                        }
                        
                    }
                    if(found)
                        break;
                }
            }

            return matches;
        }

        public static Dictionary<string, List<string>> GetMatchesOldSchool(List<string> inputs, List<string> values)
        {
            Dictionary<string, List<string>> matches = new Dictionary<string, List<string>>();

            foreach (string input in inputs)
            {
                SortedList<int, List<string>> rank = new SortedList<int, List<string>>();
                
                foreach (string value in values)
                {
                    int distance = Traditional(input, value);
                    if(rank.ContainsKey(distance))
                    {
                        rank[distance].Add(value);
                    }
                    else
                    {
                        rank.Add(distance, new List<string>(new string[] {value}));
                    }
                }

                int leastDistance = rank.Keys[0];
                matches.Add(input, rank[leastDistance]);
            }

            return matches;
        }

        public static Dictionary<string, List<string>> GetMatchesRevised(List<string> inputs, List<string> values)
        {
            Dictionary<string, List<string>> matches = new Dictionary<string, List<string>>();

            foreach (string input in inputs)
            {
                SortedList<int, List<string>> rank = new SortedList<int, List<string>>();

                foreach (string value in values)
                {
                    int distance = EditDistance(input, value);
                    if (rank.ContainsKey(distance))
                    {
                        rank[distance].Add(value);
                    }
                    else
                    {
                        rank.Add(distance, new List<string>(new string[] { value }));
                    }
                }

                int leastDistance = rank.Keys[0];
                matches.Add(input, rank[leastDistance]);
            }

            return matches;
        }

        public static Dictionary<string, List<string>> GetMatchesSift(List<string> inputs, List<string> values)
        {
            Dictionary<string, List<string>> matches = new Dictionary<string, List<string>>();

            foreach (string input in inputs)
            {
                SortedList<int, List<string>> rank = new SortedList<int, List<string>>();

                foreach (string value in values)
                {
                    int distance = Similarity(input, value);
                    if (rank.ContainsKey(distance))
                    {
                        rank[distance].Add(value);
                    }
                    else
                    {
                        rank.Add(distance, new List<string>(new string[] { value }));
                    }
                }

                int leastDistance = rank.Keys[0];
                matches.Add(input, rank[leastDistance]);
            }

            return matches;
        }

        #endregion
    }

   
}
